/*
2019.9.15
*/ 
#include<iostream>
#include<vector>
#include<string>
using std::cout;
using std::endl;
using std::cin;
using std::vector;
using std::string;
class Solution {
public:
    static bool isValid(string s) 
	{
		if(s.size()==0)
		{
			return true;	
		} 
		if(s.size()%2==1)
		{
			return false;
		}
		
		vector<char> vec;
		
		for(int i=0;i<s.size();i++)
		{
			if(vec.empty())
			{
				vec.push_back(s[i]);
			}
			else if( !match(vec[vec.size()-1],s[i]) )
			{
				vec.push_back(s[i]);
			}
			else
			{
				vec.pop_back();
			}
		}
		if(vec.empty())
		{
			return true;
		}
		return false;
	}
	
	
	static bool match(char a,char b)
	{
		if( (a=='{'&&b=='}')||(a=='('&&b==')') || (a=='['&&b==']') )
		{
			return true;
		}
		
		return false;	
	}
	
};


int main()
{
	string s="()[]{}";
	Solution solution;
	cout<<solution.isValid(s)<<endl;
	
	return 0;
}
